import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

import static java.lang.Math.pow;

/**
 * Created with IntelliJ IDEA.
 * Description:在排序数组中找元素的第一个和最后一个位置（二分模板）、搜索插入位置、山脉数组峰值索引、寻找峰值、搜索旋转排序数组
 * Date: 2024-02-18
 * Time:8:26
 */
public class Solution {
    //在排序数组中找元素的第一个和最后一个位置
    public int[] searchRange(int[] nums, int target) {
        int left = 0,right = nums.length - 1;
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;
        if(nums.length == 0) return ret;

        //查找左端点
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else if(nums[mid] >= target) right = mid;
        }
        if(nums[left] == target) ret[0] = left;
        else return ret;

        //查找右端点
        right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left +1) / 2;
            if(nums[mid] <= target) left = mid;
            else if(nums[mid] > target) right = mid - 1;
        }
        ret[1] = left;
        return ret;
    }
    ///////////////////////////////////////////////
    //x 的平方根
    public int mySqrt(int x) {
        if (x < 1) return 0;
        long left = 1, right = x;
        while (left < right) {
            long mid = left + (right - left + 1) / 2;
            if (mid * mid > x) right = mid - 1;
            else if (mid * mid < x) left = mid;
            else return (int) mid;
        }
        return (int) left;
    }
    ////////////////////////////////////////////
    //搜索插入位置
    public int searchInsert(int[] nums, int target) {
        int left = 0,right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] >= target) right = mid;
            else left = mid+1;
        }
        if(nums[left] >= target) return left;
        else return nums.length;
    }
    ///////////////////////////////////////////////
    //山脉数组峰值索引
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0,right = arr.length - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(arr[mid + 1] < arr[mid]) right = mid;
            else left = mid + 1;
        }
        return left;
    }
    ////////////////////////////////////
    //寻找峰值
    public int findPeakElement(int[] nums) {
        int left = 0,right = nums.length-1;
        while(left < right) {
            int mid = left + (right - left +1) / 2;
            if(nums[mid - 1] < nums[mid]) left = mid;
            else right = mid - 1;
        }
        return left;
    }
/////////////////////////////////////////////////
    //搜索旋转排序数组
    public int search(int[] nums, int target) {
        if(target == nums[0]) return 0;
        int left = 0,right = nums.length-1;
        //找到大于 nums[0] 的最后一个元素
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] > nums[0]) left = mid;
            else right = mid - 1;
        }
        if(target > nums[0]) left = 0;
        else {
            left++;
            right = nums.length - 1;
        }
        while(left <= right) {
            int mid = left+(right - left)/2;
            if(nums[mid] < target) left = mid + 1;
            else if(nums[mid] > target) right = mid - 1;
            else return mid;
        }
        return -1;
    }
    ////////////////////////////////////////////////////
    //寻找旋转排序数组的最小值
    public int findMin(int[] nums) {
        int left = 0,right = nums.length-1;
        //找到大于 nums[0] 的最后一个元素
        while(left < right) {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] > nums[0]) left = mid;
            else right = mid - 1;
        }
        if(left == nums.length - 1) return nums[0];
        else return nums[left + 1];
    }
    ////////////////////////////////////////////////
    //两数之和
    public int[] twoSum(int[] nums, int target) {
        int[] ret = new int[2];
        int left = 0,right = nums.length-1;
        HashMap<Integer,Integer> map = new HashMap<>();  //将原数组的元素和下标放进哈希表
        for(int i = 0;i < nums.length;i++) {  //边查找边放元素，可以防止 put 重复元素时覆盖原先的 value
            if(map.containsKey(target - nums[i])) {
                ret[0] = i;
                ret[1] = map.get(target - nums[i]);
                break;
            }
            map.put(nums[i],i);  //当前哈希表没有符合条件的数
        }
        return ret;
    }
    //////////////////////////////////////////////////
    //多数元素
    public int majorityElement(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < nums.length;i++) {
            if(!map.containsKey(nums[i]))  map.put(nums[i],1);
            else map.put(nums[i],map.get(nums[i])+1);
        }
        for(Map.Entry<Integer,Integer> entry:map.entrySet()) {
            if(entry.getValue() > nums.length/2) return entry.getKey();
        }
        return -1;
    }
    ////////////////////////////////////////////
    //法一：二分查找
    public static int takeAttendance1(int[] records) {
        //法一：二分查找
        int left = 0,right = records.length - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(records[mid] - mid == 1) right = mid;
            else left = mid + 1;
        }
        if(records[left] - left == 0) return records.length;
        return left;
    }

    //法二：哈希表
/*
    public static int takeAttendance2(int[] records) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < records.length; i++) {
            map.put(records[i],i);
        }
    }
*/




}
